package a_doubleWrite;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * 课程表2，生成学习的顺序序列
 *
 * @author luolidong
 * @version 1.0
 * @create 2021-07-30 14:47
 */
public class L210 {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        if (numCourses == 0) return new int[0];
        //拓扑排序
        //优化：使用set保存i，对应的指向节点
        HashSet<Integer>[] set = new HashSet[numCourses];
        for (int i = 0; i <numCourses ; i++) {
            set[i]=new HashSet<>();
        }
        //1.创建入度数组,因为0到num-1
        int[] inDegrees = new int[numCourses];
        for (int[] p : prerequisites) {
            inDegrees[p[0]]++;
            set[p[1]].add(p[0]);//注意保存的是：[0,1] 1->0
        }
        //2.创建保存入度为0的队列
        Queue<Integer> queue = new LinkedList<>();
        //入度为0,入队
        for (int i = 0; i < numCourses; i++) {
            if (inDegrees[i] == 0) queue.offer(i);
        }
        //记录入队节点总数
        int count = 0;
        int[] res = new int[numCourses];
        //bfs,入队，出队
        while (!queue.isEmpty()) {
            int poll = queue.poll();
            res[count] = poll;
            count++;

            //该poll节点指向的节点的入度数-1

//            for (int[] p : prerequisites) {
//                if (p[1] == poll) {
//                    inDegrees[p[0]]--;
//                    //再次判断入度数为0的，入队
//                    if (inDegrees[p[0]] == 0) {
//                        queue.offer(p[0]);
//                    }
//                }
//            }

//            优化通过set获取，不用每次遍历
            for (int i : set[poll]) {
                inDegrees[i]--;
                if (inDegrees[i] == 0) {
                    queue.offer(i);
                }
            }
        }
        if (count == numCourses) {
            return res;
        }
        return new int[0];
    }
}
